<html>
<head><meta charset="utf-8"><title>Range::binary_search_by · t-libs · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/index.html">t-libs</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/Range.3A.3Abinary_search_by.html">Range::binary_search_by</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="221837079"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/Range%3A%3Abinary_search_by/near/221837079" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Simon Sapin <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/Range.3A.3Abinary_search_by.html#221837079">(Jan 06 2021 at 23:18)</a>:</h4>
<p>Binary search is notoriously tricky to get right, so it’s great that we have it implemented for slices. However I’ve had a couple cases where I’d like to use binary search to search something that is not a contiguous slice. Or it is a slice but the key function wants to know the index.</p>



<a name="221837114"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/Range%3A%3Abinary_search_by/near/221837114" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Simon Sapin <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/Range.3A.3Abinary_search_by.html#221837114">(Jan 06 2021 at 23:19)</a>:</h4>
<p>Any thoughts on whether <code>binary_search_by</code> and <code>binary_search_by_key</code> methods for <code>Range&lt;usize&gt;</code> would be a good fit for the standard library?</p>



<a name="221838823"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/Range%3A%3Abinary_search_by/near/221838823" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> scottmcm <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/Range.3A.3Abinary_search_by.html#221838823">(Jan 06 2021 at 23:39)</a>:</h4>
<p>Once it's decoupled from indexing it could search any quantized space, right?  At that point just supporting <code>Range&lt;usize&gt;</code> feels a bit odd.</p>



<a name="221841773"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/Range%3A%3Abinary_search_by/near/221841773" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Simon Sapin <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/Range.3A.3Abinary_search_by.html#221841773">(Jan 07 2021 at 00:15)</a>:</h4>
<p>Sure it could be more generic than usize, but I suspect expressing the trait bounds gets annoying</p>



<a name="221841930"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/Range%3A%3Abinary_search_by/near/221841930" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Simon Sapin <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/Range.3A.3Abinary_search_by.html#221841930">(Jan 07 2021 at 00:17)</a>:</h4>
<p>The current code uses <code>==</code>, <code>&gt;</code>, <code>/</code>, <code>+</code>, and <code>-=</code></p>



<a name="221844038"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/Range%3A%3Abinary_search_by/near/221844038" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> cuviper <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/Range.3A.3Abinary_search_by.html#221844038">(Jan 07 2021 at 00:45)</a>:</h4>
<p>it also uses literals 0, 1, 2</p>



<a name="221848892"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/Range%3A%3Abinary_search_by/near/221848892" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> scottmcm <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/Range.3A.3Abinary_search_by.html#221848892">(Jan 07 2021 at 02:05)</a>:</h4>
<p>Could <code>Step</code> do it?  Wouldn't seem terrible if it only worked for the types where <code>Range&lt;T&gt;: Iterator</code>...</p>
<p>Though as you say, I don't know how essential it would be to support other types.</p>



<a name="221848956"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/Range%3A%3Abinary_search_by/near/221848956" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> scottmcm <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/Range.3A.3Abinary_search_by.html#221848956">(Jan 07 2021 at 02:06)</a>:</h4>
<p>Is the thing you'd like to search another container?</p>



<a name="221850476"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/Range%3A%3Abinary_search_by/near/221850476" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Steven Fackler <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/Range.3A.3Abinary_search_by.html#221850476">(Jan 07 2021 at 02:34)</a>:</h4>
<p>I've written something like this before, yeah.</p>



<a name="221863342"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/Range%3A%3Abinary_search_by/near/221863342" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Simon Sapin <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/Range.3A.3Abinary_search_by.html#221863342">(Jan 07 2021 at 07:15)</a>:</h4>
<p><span class="user-mention silent" data-user-id="125270">scottmcm</span> <a href="#narrow/stream/219381-t-libs/topic/Range.3A.3Abinary_search_by/near/221848956">said</a>:</p>
<blockquote>
<p>Is the thing you'd like to search another container?</p>
</blockquote>
<p>The recent case is reading an mmap’ed file in some binary format, I suppose you could view it as a custom container. I don’t remember what the other case was.</p>



<a name="221938092"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/Range%3A%3Abinary_search_by/near/221938092" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> BurntSushi <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/Range.3A.3Abinary_search_by.html#221938092">(Jan 07 2021 at 12:55)</a>:</h4>
<p>yeah i've always found Go's binary search to be much more flexible: <a href="https://golang.org/pkg/sort/#Search">https://golang.org/pkg/sort/#Search</a></p>
<p>i've had to implement it a couple of times: <a href="https://github.com/BurntSushi/regex-automata/blob/4e0e8ec599e92b115c53ed8d760f7c38bf91891f/src/nfa/range_trie.rs#L568-L577">https://github.com/BurntSushi/regex-automata/blob/4e0e8ec599e92b115c53ed8d760f7c38bf91891f/src/nfa/range_trie.rs#L568-L577</a> and <a href="https://github.com/BurntSushi/regex-automata/blob/6682f9cef5b4ef0c0892c4a6589658cd171106d8/src/sparse.rs#L1233-L1239">https://github.com/BurntSushi/regex-automata/blob/6682f9cef5b4ef0c0892c4a6589658cd171106d8/src/sparse.rs#L1233-L1239</a></p>



<a name="221984972"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/Range%3A%3Abinary_search_by/near/221984972" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> scottmcm <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/Range.3A.3Abinary_search_by.html#221984972">(Jan 07 2021 at 18:57)</a>:</h4>
<p>Looks like the version of this I wrote is also over <code>usize</code>: <a href="https://github.com/scottmcm/uax/blob/7a82b89312c0f3bfa5cde1a59b761a40ac0dfa5a/src/lookup_table.rs#L39-L55">https://github.com/scottmcm/uax/blob/7a82b89312c0f3bfa5cde1a59b761a40ac0dfa5a/src/lookup_table.rs#L39-L55</a></p>
<p>(Although, looking again, I'm not sure I couldn't have just used the slice one...)</p>



<a name="221993954"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/Range%3A%3Abinary_search_by/near/221993954" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> cuviper <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/Range.3A.3Abinary_search_by.html#221993954">(Jan 07 2021 at 20:09)</a>:</h4>
<p>I've written variants of bisect / binary search for root-finding before, which definitely goes beyond slices or <code>Range&lt;usize&gt;</code></p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>